In computer science, a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system. In most cases, a thread is a component of a process. Information on a thread has a thread ID, a program counter, a register set, and a stack to handle the service request and shares other resources such as codes, data, and files with other threads. Depending on program environment, two or more threads may be executed simultaneously and such execution method is called multithreading. Multiple threads can exist within the same process and share resources such as memory, while different processes do not share these resources.
In a multithreaded system, there is a task queue to distribute at least one task to one of multiple work threads, which contend with one another for the task. At the time, as two or more worker threads cannot access the task queue at the same time, the respective worker threads should acquire a lock to prevent other worker threads from accessing the task queue and get the task from the task queue. However, in the multithreaded system, when the number of worker threads increases, the lock contention among the multiple worker threads becomes fierce and the performance of the whole system is degraded.
FIG. 1 is a drawing illustrating a multithreaded system for assigning a task to one of the multiple worker threads through one task queue according to the prior art.
By referring to FIG. 1, the multithreaded system 100 according to the prior art includes a control thread 20, one task queue 30, and multiple worker threads 40-1, 40-2, . . . , and 40-n. 
A processor (non-illustrated) may cause the control thread 20 to receive a new task 14 and put it into the task queue 30, where tasks 11, 12, and 13 may be waiting. The processor may cause the task queue 30 to distribute the waiting tasks 11, 12, and 13 in prescribed order (e.g., FIFO) to the multiple worker threads 40-1, 40-2, . . . , and 40-n. At the time, the multiple worker threads 40-1, 40-2, . . . , and 40-n should contend with one another to get the tasks from the task queue 30 in the multithreaded system 100. At the time, as two or more threads cannot access the task queue 30 at the same time, the control thread 20 and the respective worker threads 40-1, 40-2, . . . , and 40-n must acquire a lock to prevent other threads from accessing the task queue 30 and put the new task 14 into the task queue 30 or get tasks 11, 12, and 13 from the task queue 30. In particular, the respective worker threads 40-1, 40-2, . . . , and 40-n should contend not only with the control thread 20 but also with other worker threads to preoccupy the task queue 30. Thus, if the number of worker threads 40-1, 40-2, . . . , and 40-n increases, the performance of the whole system may be degraded.
Accordingly, a new technology is required to minimize the lock contention among worker threads even though the number of worker threads increases in the multithreaded system.